\chapter{Вопрос № 23}

Композиционная формула, комбинаторный смысл, простейшие примеры. Количество помеченных графов и количество помеченных связынх графов. Разбиение множества, числа Белла. Комбинаторный смысл композиционной формулы в случае $b_k = t^k$.

\section{Композиционная формула}

Смысл формулы $$ H\left(x\right) = e^{F\left(x\right)} $$ заключается в том, чтобы разбить множество на блоки, а затем в каждом блоке совершить некоторое комбинаторное действие, можно обобщить эту формулу, заменив композицию эпф $e^x$ и $F\left(x\right)$ на композицию произвольных эпф $G\left(x\right)$ и $F\left(x\right)$.

Введем несколько обозначений:
\[
	\begin{split}
		& F\left(x\right) = a_1x + a_2\frac{x^2}{2} + a_3\frac{x^3}{3!} + ... \\
		& G\left(x\right) = 1 + b_1 x + b_2\frac{x^2}{2} + b_3\frac{x^3}{3!} + ...
	\end{split}
\]
тогда композиционная формула:
\begin{equation}
	H\left(x\right) = G\left(F\left(x\right)\right)
\end{equation}
имеет следующий комбинаторный смысл: множество разбивается на произвольное количество блоков, внутри каждого блока мощностью $i$ совершается некоторое действие $a_i$ числом способов, а затем над $k$ получившимися блока совершается некоторое действие $b_k$ способами.

\section{Пример использования композиционной формулы}

Рассмотрим следующую задачу, имеется $n$ людей, требуется посчитать количество способов, которыми этих людей можно разбить на непустые группы, линейно упорядочить людей в каждой группе, а затем циклически упорядочить все группы.

Линейно упорядочить $n$ человек можно $n!$ способами, а значит:
\[
	F\left(x\right) = \sum_{n=1}^\infty n! \frac{x^n}{n!} = \frac{x}{1-x}
\]
а циклически упорядочить $k$ блоков можно $\left(k-1\right)!$ способами, а значит:
\[
	G\left(x\right) = ln\left(\frac{1}{1-x}\right) + 1
\]
а вся композиция выглядит следующим образом:
\[
	\begin{split}
		& H\left(x\right) = 1+ ln\left(\frac{1}{1-\frac{x}{1-x}}\right) = 1 + ln\left(\frac{1-x}{1-2x}\right) = \\
		& = 1 - ln\left(\frac{1}{1-x}\right) + ln\left(\frac{1}{1-2x}\right)
	\end{split}
\]
откуда получаем, что:
\[
	\begin{split}
		& c_0 = 1 \\
		& c_n = 2^n\left(n-1\right)! - \left(n-1\right)!
	\end{split}
\]

\section{Перечисление помеченных графов}

Помеченный граф - граф, все вершины которого пронумерованы. Пусть имеется $n$ вершин, сколькими способами можно провести между ними ребра? Всего различных пар вершин $$ \binom{n}{2} $$, каждая пара может образовывать или необразовывать ребро, т. е. всего: $$ 2^{\binom{n}{2}} $$. Таким образом найдено число всех помеченных графов на $n$ вершинах, теперь используя экспоненциальную формулу найдем число связных помеченных графов на $n$ вершинах.

Пусть
\[
	F\left(x\right) = a_1 x + a_2\frac{x^2}{2} + a_3 \frac{x^3}{3!} + ...
\]
- эпф описывающая связные помеченные графы, тогда эпф перечисляющая все помеченные графы определяется соотношением:
\[
	H\left(x\right) = 1 + c_1 x + c_2 \frac{x^2}{2} + c_3 \frac{x^3}{3!} + ... = e^{F\left(x\right)}
\]
теперь продифференцируем левую и правую часть:
\[
	\begin{split}
		& H'\left(x\right) = c_1 + c_2 x + c_3 \frac{x^2}{2} + c_3\frac{x^3}{3!} + ... = H\left(x\right)F'\left(x\right) = \\
		& = \left(1 + c_1 x + c_2 \frac{x^2}{2} + c_3 \frac{x^3}{3! } + ... \right)\left(a_1 + a_2 x + a_3 \frac{x^2}{2} + a_4 \frac{x^3}{3!} + ... \right)
	\end{split}
\]
откуда по определению произведения эпф:
\[
	c_{n+1} = \sum_{i=0}^{n}\binom{n}{i} c_i a_{n-i+1} = a_{n+1} + \sum_{i=0}^{n-1} \binom{n}{i} a_i c_{n-i+1}
\]
вместе с начальными условиями:
\[
	\begin{split}
		& c_0 = 1; a_0 = 0;\\
		& c_1 = 1; a_1 = 1;\\
	\end{split}
\]
получаем рекуррентное соотношение перечисляющее количество связных помеченных графов:
\begin{equation}
	\begin{split}
		& a_{n+1} = c_{n+1} - \sum_{i=0}^{n-1} \binom{n}{i} a_i c_{n-i+1} \\
		& c_n = 2^{\binom{n}{2}}
	\end{split}
\end{equation}

\section{Числа Белла}

Если в качестве $F\left(x\right)$ в экспоненциальной формуле взять функцию:
\[
	F\left(x\right) = \sum_{i=1}^\infty \frac{x^i}{i!} = e^x - 1
\]
то мы получаем эпф числа различных разбиений множества на непустые блоки (согласно смыслу экспоненциальной формулы), но эти числа называются чслами Белла, а значит эпф для чисел Белла:
\begin{equation}
	F\left(x\right) = B_0 + B_1 x + B_2 \frac{x^2}{2} + B_3 \frac{x^3}{3!} + ... = exp\left(e^x - 1\right)
\end{equation}
рекуррентное соотношение для чисел Белла:
\begin{equation}
	B_{n+1} = \sum_{i=0}^n \binom{n}{i} B_i
\end{equation}

\section{Фиксированное число компонент связности}

Воспользуемся тем, что коэффициенты производящих функций могут иметь произвольный смысл и в качестве коэффициентов в функции $G\left(x\right)$ в композиционной формуле возьмем метки $t^k$, тогда:
\[
	G\left(F\left(x\right)\right) = 1+ t^1F\left(x\right) + t^2 \frac{F^2\left(x\right)}{2} + t^3 \frac{F^3\left(x\right)}{3!} + ... = H\left(x,t\right)
\]
воспринимая $t$ как переменную приведем подобные слагаемые и получим:
\[
	H\left(x,t\right) = 1 + c_1\left(t\right)x + c_2\left(t\right)\frac{x^2}{2!} + c_3\left(t\right)\frac{x^3}{3!} + ...
\]
где
\[
	c_n\left(t\right) = \sum_{k=0}^n c\left(n,k\right) t^k
\]
Комбинаторный смысл $c\left(n,k\right)$ - количество способов разбить $n$-множество ровно на $k$ блоков, а затем в каждом из $k$ блоков совершить некоторое комбинаторное действие.
